0% completed
Problem Statement
Given four arrays of integers nums1, nums2, nums3, and nums4 of the same length n, return the count of tuples (i, j, k, l) such that:
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
Examples
Example 1:
- Input: nums1 = [1], nums2 = [-1], nums3 = [0], nums4 = [0]
- Expected Output: 1
- Justification: The one quadruplet that sum up to 0 is:
- (1, -1, 0, 0)
Example 2:
- Input: nums1 = [0, 1], nums2 = [1, -1], nums3 = [-1, 0], nums4 = [1, -1]
- Expected Output: 4
- Justification: The four quadruplets that sum up to 0 are:
- (0, 1, 0, -1)
- (0, -1, 0, 1)
- (1, -1, -1, 1)
- (1, 1, -1, -1)
Example 3:
- Input: nums1 = [-1, 3], nums2 = [2, -3], nums3 = [3, 4], nums4 = [-4, -3]
- Expected Output: 3
- Justification: The three quadruplets that sum up to 0 are:
- (-1, 2, 3, -4)
- (3, -3, 4, -4)
- (3, -3, 3, -3)
Solution
To solve this problem, we'll leverage a hash map to efficiently find pairs that sum up to the target value, which is zero in this case. The rationale behind using a hash map is to store the sum of pairs from the first two arrays along with their frequency. This way, we can quickly look up the complement of these sums in the hash map when iterating through pairs from the last two arrays. This approach significantly reduces the time complexity compared to a brute force solution, which checks every possible quadruplet.
The effectiveness of this approach lies in its ability to transform the problem from a four-array problem into two, two-array problems, thereby simplifying the process of finding the target sum. By focusing on sums rather than individual elements, we can more easily identify combinations that meet our criteria, making this method both efficient and scalable for larger input sizes.
Step-by-Step Algorithm
-
Initialize a Hash Map: Create an empty hash map (
sumMap) to store the sum of each pair fromnums1andnums2as keys and their frequency (number of times the sum occurs) as values. -
Compute Sums of Pairs from
nums1andnums2:- Iterate over each element in
nums1using a loop. - For each element in
nums1, iterate over each element innums2using another loop. - Calculate the sum of the current elements from
nums1andnums2. - Update
sumMapwith this sum. If the sum already exists as a key insumMap, increment its value by 1. Otherwise, add the sum as a new key with the value of 1.
- Iterate over each element in
-
Count Quadruplets:
- Initialize a counter (
count) to 0. This will track the number of quadruplets that sum to 0. - Iterate over each element in
nums3using a loop. - For each element in
nums3, iterate over each element innums4using another loop. - For the current elements from
nums3andnums4, calculate the sum that would be needed fromnums1andnums2for the total four elements to sum to 0. This is the negation of the sum of the current elements fromnums3andnums4. - Check if this required sum exists as a key in
sumMap. If it does, add the corresponding value (frequency) fromsumMaptocount.
- Initialize a counter (
-
Return Result: Return the
countvariable, which now contains the total number of quadruplets that sum to 0.
Algorithm Walkthrough
Let's consider the Input: nums1 = [0, 1], nums2 = [1, -1], nums3 = [-1, 0], nums4 = [1, -1].
-
Initialize
sumMap: Let's start with an empty hash map. -
Compute Sums of Pairs from
nums1andnums2:- Pair
0fromnums1with1fromnums2to get sum1. UpdatesumMap:{1: 1}. - Pair
0fromnums1with-1fromnums2to get sum-1. UpdatesumMap:{1: 1, -1: 1}. - Pair
1fromnums1with1fromnums2to get sum2. UpdatesumMap:{1: 1, -1: 1, 2: 1}. - Pair
1fromnums1with-1fromnums2to get sum0. UpdatesumMap:{1: 1, -1: 1, 2: 1, 0: 1}.
- Pair
-
Count Quadruplets:
- Pair
-1fromnums3with1fromnums4. The required sum fromnums1andnums2is0(since-1 + 1 = 0, we need0fromnums1andnums2to sum to0).sumMaphas0: 1, so incrementcountby1. - Pair
-1fromnums3with-1fromnums4. The required sum is2.sumMaphas2: 1, so incrementcountby1. - Pair
0fromnums3with1fromnums4. The required sum is-1.sumMaphas-1: 1, so incrementcountby1. - Pair
0fromnums3with-1fromnums4. The required sum is1.sumMaphas1: 1, so incrementcountby1.
- Pair
-
Return Result: The final
countis4, indicating there are 4 quadruplets across the four arrays that sum to 0.
Code
Complexity Analysis
Time Complexity
- Computing Sums of Pairs: The first part of the algorithm involves iterating over two loops to compute the sums of elements from
nums1andnums2, and then fromnums3andnums4. Each pair of arrays involvesoperations where (n) is the length of the array. Since we do this for two pairs of arrays, the time complexity for this part is . - Looking Up Sums: The second part involves looking up the negative of these sums in the hash map for pairs from
nums3andnums4. This also results inoperations, but the lookup time is on average for hash maps, leading to for this part.
The overall time complexity of the algorithm is therefore
Space Complexity
- Hash Map Storage: The space complexity is primarily due to the storage of sum frequencies in a hash map. In the worst case, all pair sums are unique, leading to
space complexity due to the storage of these sums.
Therefore, the overall space complexity of the algorithm is
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity